package src;

public class Heap<T extends Comparable<T>> {
    public int[] heap;
    public int SIZE;
    public int count;

    Heap(int size) {
        SIZE = size;
        // reference: https://stackoverflow.com/questions/34827626/cannot-be-cast-to-ljava-lang-comparable
        heap = new int[SIZE];
        count = 0;
    }

    public Heap(int[] heap) {
        this.heap = heap;
        SIZE = heap.length;
        this.count = 0;
    }

    public void setHead(int value) {
        heap[0] = value;
    }

    public int getHead() {
        return heap[0];
    }

    public int[] getHeap() {
        return heap;
    }

    //大顶堆
    public void add(int item) {
        if (count >= SIZE) {
            // throw new Exception("src.Heap Overflow");
            System.out.println("src.Heap Full");
            return;
        }
        heap[heap.length] = item;
        compareParent(heap.length - 1, false);
    }

    /**
     * 对比大小，对调位置
     *
     * @param index
     * @param isCompareBig 父节点比较大？
     */
    private int compareParent(int index, boolean isCompareBig) {
        int cIndex = getParentIndex(index);
        int compareNode;
        //当前节点
        int current;
        try {
            compareNode = heap[cIndex];
            current = heap[index];
        } catch (Exception e) {
            return index;
        }
        //对比节点的值比当前节点小
        if (isCompareBig ? compareNode > current : compareNode < current) {
            //互换位置
            heap[cIndex] = current;
            heap[index] = compareNode;
            //此时的cIndex是当前节点的位置
            return compareParent(cIndex, isCompareBig);
        } else {
            return index;
        }
    }

    // 完善delete函数
    public void delete() {
        if (heap.length == 0) {
            System.out.println("堆为空");
            return;
        }
        //最后的值拉到最前面
        heap[0] = heap[heap.length - 1];
        compareSon(0);
        //重新排序
//        SortTree();
    }


    /**
     * @param index
     */
    public void compareSon(int index) {
        int compare = heap[index];
        int left = getLeftIndex(index);
        int right = getRightIndex(index);
        if (left > heap.length - 1 || right > heap.length - 1) {
            return;
        }
        int leftValue = heap[left];
        int rightValue = heap[right];
        if (compare < leftValue) {
            heap[left] = compare;
            heap[index] = leftValue;
            compareSon(left);
        } else if (compare < rightValue) {
            heap[right] = compare;
            heap[index] = rightValue;
            compareSon(right);
        }
    }

    /**
     * 层级遍历
     */
    // 为了测试方便，完善print函数
    public void print() {
        int index = 0;
        for (int level = 1; level <= heap.length / 2; level++) {
            System.out.print("\n第" + level + "层的元素有：");
            for (int j = 0; j < Math.pow(2, (level - 1)); j++) {
                try {
                    System.out.print(heap[index++] + "\t\t");
                } catch (ArrayIndexOutOfBoundsException e) {
                    System.out.println("\n");
                    return;
                }
            }
        }
    }

    /**
     * 降序
     */
    public void heapDdescendingSort() {
        for (int i = heap.length / 2 - 1; i >= 0; i--) {
            descendingSort(i);
        }
    }

    /**
     * 降序
     *
     * @param index
     */
    private void descendingSort(int index) {
        int leftIndex = getLeftIndex(index);
        int rightIndex = getRightIndex(index);
        //在范围里
        if (leftIndex < heap.length && rightIndex < heap.length) {
            if (heap[index] < heap[leftIndex] && heap[leftIndex] > heap[rightIndex]) {
                swapValue(index, leftIndex);
            } else if (heap[index] < heap[rightIndex] && heap[rightIndex] > heap[leftIndex]) {
                swapValue(index, rightIndex);
            }
        } else if (leftIndex < heap.length && heap[index] < heap[leftIndex]) {
            swapValue(index, leftIndex);
        } else if (rightIndex < heap.length && heap[index] < heap[rightIndex]) {
            swapValue(index, rightIndex);
        }
    }

    /**
     * 升序
     */
//    public void heapAscendingSort() {
//        for (int i = heap.length / 2 - 1; i >= 0; i--) {
//            ascendingSort(i);
//        }
//    }
//
    /**
     * 升序
     *
     * @param index
     */
//    public void ascendingSort(int index) {
//        int leftIndex = getLeftIndex(index);
//        int rightIndex = getRightIndex(index);
//        //在范围里
//        if (leftIndex < heap.length && rightIndex < heap.length) {
//            if (heap[index] > heap[leftIndex] && heap[leftIndex] > heap[rightIndex]) {
//                //要对比的值比左节点大，而且左节点比右节点大
//                swapValue(index, leftIndex);
//            } else if (heap[index] > heap[rightIndex] && heap[rightIndex] > heap[leftIndex]) {
//                //要对比的值比右节点大，而且右节点比左节点大
//                swapValue(index, rightIndex);
//            }
//        } else if (leftIndex < heap.length && heap[index] > heap[leftIndex]) {
//            //存在左节点，而且要对比的值比左节点大
//            swapValue(index, leftIndex);
//        } else if (rightIndex < heap.length && heap[index] > heap[rightIndex]) {
//            //存在右节点，而且要对比的值比右节点大
//            swapValue(index, rightIndex);
//        }
//    }

    private void swapValue(int index, int swap) {
        int temp;
        temp = heap[swap];
        heap[swap] = heap[index];
        heap[index] = temp;
        descendingSort(swap);
    }

    private int getLeftIndex(int i) {
        return ((i + 1) << 1) - 1;
    }

    private int getRightIndex(int i) {
        return (i + 1) << 1;
    }

    private int getParentIndex(int i) {
        return ((i + 1) >> 1) - 1;
    }
}